import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * Created by L.jp
 * Description:给定一个节点数为n的无序单链表，对其按升序排序。
 * User: 86189
 * Date: 2022-05-22
 * Time: 19:27
 */
//class ListNode {
//    int val;
//    ListNode next = null;
//    public ListNode(int val){
//        this.val=val;
//    }
//  }
public class Solution {
    public ListNode sortInList (ListNode head) {
        //方法一：借助优先级队列排序
        PriorityQueue<ListNode> priorityQueue=new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        while (head!=null){
            priorityQueue.add(head);
            head=head.next;
        }
        ListNode res=new ListNode(-1);
        ListNode cur=res;
        while (!priorityQueue.isEmpty()){
            cur.next=priorityQueue.poll();
            cur=cur.next;
        }
        //原来加入堆的时候各个指向之间是没有断开的，重新构造链表之后cur这个时候就到了最后一个节点，需要断开原来的指向
        cur.next=null;
        return res.next;
    }
}
